package main

import "fmt"

//1、不要用最之前的挨个将0变成1然后求最大面积，会超时
//2、超出内存，需要再修改下，用map存储个数以及对应面积，原切片记录个数顺序
//3、第一轮遍历时将陆地直接标记为陆地个数，不要二次遍历再修改这样会超时
//第一次通过用时13%，内存76%
//使用匿名函数，减少内存占用，定义结构体减少重复判断次数，将判断条件前移，用时23%，内存81%
//用bool类型，判断map里面是否已经有该面积，如果没有，直接增加面积，减少之后重复循环，用时61%，内存76%
func largestIsland(grid [][]int) int {
	var largestarea int
	num := 2
	var area int
	n := len(grid)
	dir4 := []struct{ x, y int }{{x: -1, y: 0}, {1, 0}, {0, -1}, {0, 1}}
	var dfs func(int, int)
	dfs = func(i, j int) {
		grid[i][j] = num
		area++
		for _, d := range dir4 {
			x, y := i+d.x, j+d.y
			if 0 <= x && x < len(grid) && 0 <= y && y < len(grid) && grid[x][y] == 1 {
				dfs(x, y)
			}
		}
	}
	gridMap := map[int]int{}
	for i, v := range grid {
		for j := range v {
			if grid[i][j] == 1 {
				area = 0
				num++
				dfs(i, j)
				gridMap[num] = area
			}
		}
	}
	var tmpMap map[int]bool
	tmp := 0
	for i, v := range grid {
		for j, v1 := range v {
			if v1 == 0 {
				tmp = 0
				//用bool类型，判断map里面是否已经有该面积，如果没有，直接增加面积，减少之后重复循环
				tmpMap = map[int]bool{}
				for _, d := range dir4 {
					x, y := i+d.x, j+d.y
					if 0 <= x && x < n && 0 <= y && y < n && grid[x][y] > 0 && !tmpMap[grid[x][y]] {
						tmpMap[grid[x][y]] = true
						tmp += gridMap[grid[x][y]]
					}
				}
				if tmp > largestarea {
					largestarea = tmp
				}
			}
		}
	}
	if largestarea == 0 && grid[0][0] > 0 {
		return n * n
	}
	return largestarea + 1
}

func main() {
	grid := [][]int{{1, 0}, {0, 1}}
	fmt.Println(largestIsland(grid))

	//range也可以只用一个参数接收，此时接收的是索引
	// for i := range grid {
	// 	fmt.Println(i)
	// }

	//给切片赋值都要用append
	// gridMap := {][]map[int]int{}
	// gridMap = append(gridMap, []map[int]int{})
	// gridMap[0] = append(gridMap[0], map[int]int{})
	// gridMap[0][0] = map[int]int{1: 2}

	// gridMap := [][]int{}
	// gridMap = append(gridMap, []int{})
	// gridMap[0] = append(gridMap[0], 1)
}
